package utils;

import graph.Edge;
import graph.Graph;
import graph.Subgraph;
import graph.UndirectedGraph;
import graph.Vertex;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * An object from which random graphs may be generated.
 * @author Alex
 *
 */
public class GraphUtils {
	
	/**
	 * Creates a new object from which to generate random graphs.
	 */
	public GraphUtils() {
		
	}
	
	/**
	 * This method makes a random graph, given a number of vertices and edges
	 * @param numVertices Number of vertices to place in graph.
	 * @param numEdges Number of edges to place in graph.
	 * @param connected True if the graph should be connected.
	 * @return A graph object with edges placed at random.
	 * @throws Exception If numEdges exceeds n(n-1)/2, or if connected is true and there are not enough
	 * edges to connect the number of vertices specified.
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public Graph<String, Double> generateUndirectedGraph(int numVertices, int numEdges, boolean connected) throws Exception {
		if(numEdges > ((numVertices * (numVertices -1)) / 2))
			throw new Exception("Number of edges exceeds limit for " + numVertices + " vertices!");
		if(connected && (numEdges < (numVertices - 1)))
			throw new Exception("Not enought edges to make a connected graph!");
		
		Graph<String, Double> g;
		List<Vertex<String>> vList = new ArrayList<Vertex<String>>();
		List<Edge<String, Double>> eList = new ArrayList<Edge<String, Double>>();
		if(connected) {
			makeConnectedComponent(numVertices, vList, eList);
			placeEdgesAtRandom(numEdges, vList, eList);
		}
		else {
			for(int i = 0; i < numVertices; i++) {
				Vertex<String> v = new Vertex<String>("v"+i);
				vList.add(v);
			}
			//Just places edges randomly between any two vertices.
			placeEdgesAtRandom(numEdges, vList, eList);
		}
		
		Set<Vertex<String>> vSet = new HashSet<Vertex<String>>();
		vSet.addAll(vList);
		Set<Edge<String, Double>> eSet = new HashSet<Edge<String, Double>>();
		eSet.addAll(eList);
		g = new UndirectedGraph(vSet, eSet);
		
		return g;
	}

	/**
	 * Use this to create a base connected component when constructing random, connected graph.
	 * @param numVertices
	 * @param vList
	 * @param eList
	 */
	private void makeConnectedComponent(int numVertices,
			List<Vertex<String>> vList, List<Edge<String, Double>> eList) {
		Random rand;
		vList.add(new Vertex<String>("v0"));
		for(int i = 1; i < numVertices; i++) {
			rand = new Random();
			int randomDraw = rand.nextInt(vList.size());
			Vertex<String> v1 = vList.get(randomDraw);
			Vertex<String> v2 = new Vertex<String>("v"+i);
			Edge<String, Double> e = new Edge<String, Double>(v1, v2);
			eList.add(e);
			vList.add(v2);
		}
	}

	/**
	 * Requires a non-empty vertex list and starts placing edges randomly between
	 * the vertices in that list.
	 * @param numEdges
	 * @param vList
	 * @param eList
	 */
	private void placeEdgesAtRandom(int numEdges, List<Vertex<String>> vList,
			List<Edge<String, Double>> eList) {
		Random rand;
		while(eList.size() < numEdges) {
			rand = new Random();
			int v1 = rand.nextInt(vList.size());
			int v2 = rand.nextInt(vList.size());
			if(v1 != v2) {
				Edge<String, Double> e = new Edge<String, Double>(vList.get(v1), vList.get(v2));
				if(!eList.contains(e))
					eList.add(e);
				else
					e = null;
			}
		}
	}
	
	/**
	 * This method takes a Graph object and partitions it into two subgraphs.
	 * @param g The Graph to partition.
	 * @return A set of Subgraphs representing a partition.
	 * @throws Exception If the union of the subgraph vertex sets does not equal the base vertex set.
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public Set<Subgraph> makePartition(Graph g) throws Exception {
		int vCount = g.getVertices().size();
		Random rand = new Random();
		int split = Math.max(1, rand.nextInt(vCount));
		Set<Vertex> leftSet, rightSet;
		leftSet = new HashSet<Vertex>();
		rightSet = new HashSet<Vertex>();
		Iterator<Vertex> iter = g.getVertices().iterator();
		for(int i = 0; i < split; i++)
			leftSet.add(iter.next());
		for(int i = split; i < vCount; i++)
			rightSet.add(iter.next());
		Subgraph leftGraph = new Subgraph((UndirectedGraph) g, leftSet);
		Subgraph rightGraph = new Subgraph((UndirectedGraph) g, rightSet);
		if(leftGraph.getVertexCount() + rightGraph.getVertexCount() != vCount)
			throw new Exception("Union of subgraphs not equal to base graph!  Left side is size " 
					+ leftGraph.getVertexCount() + ", right is size " + rightGraph.getVertexCount()
					+ " , base graph is size " + vCount);
		Set<Subgraph> partition = new HashSet<Subgraph>();
		partition.add(leftGraph);
		partition.add(rightGraph);
		return partition;
	}
	
	/**
	 * Takes a graph and partition and returns a list of degree vectors corresponding to the in and out degree of each vertex.
	 * @param baseGraph
	 * @param partition
	 * @return
	 */
	public List<DegreeVector> makeDegreeVectors(Graph<Object,Object> baseGraph, Set<Subgraph<Object, Object>> partition) {
		List<DegreeVector> vectors = new ArrayList<DegreeVector>();
		Iterator<Subgraph<Object, Object>> iter = partition.iterator();
		Subgraph<Object, Object> block_1, block_2;
		block_1 = iter.next();
		block_2 = iter.next();
		for(Vertex<Object> v : baseGraph.getVertices()) {
			double inDegree = 0, outDegree = 0;
			for(Vertex<Object> neighbor : v.getNeighbors()) {
				//this is using a pretty strong assumption - first entry of vector shows links from v to own block,
				//and second entry from v to opposite block.
				if((block_1.getVertices().contains(neighbor) && block_1.getVertices().contains(v))
						|| (block_2.getVertices().contains(neighbor) && block_2.getVertices().contains(v)))
					inDegree++;
				else
					outDegree++;
			}
			DegreeVector dv = new DegreeVector(new Double[]{inDegree, outDegree});
			vectors.add(dv);
		}
		return vectors;
	}
	
	/**
	 * Determines if a sequence of degrees is graphic using Havel and Hakimi's algorithm.
	 * @param sequence The sequence of degrees to test.
	 * @param The index of the vectors being used to give the sequence.
	 * @return True if the sequence is graphic, false otherwise.
	 */
	public boolean isGraphic(List<DegreeVector> sequence, int index) {
		if(sequence.size() == 1)
			return true;
		boolean isGraphic = true;
		List<Double> degrees = new ArrayList<Double>();
		for(DegreeVector dv : sequence)
			degrees.add(dv.getEntry(index));
		Collections.sort(degrees);
		Collections.reverse(degrees);
		while(degrees.size() > 1) {
			double numberToSubtract = degrees.get(0);
			if(numberToSubtract < 0) {
				isGraphic = false;
				break;
			}
			double subtracted = numberToSubtract;
			for(int j = 1; j <= subtracted && j < degrees.size(); j++) {
				double afterDecrement = degrees.get(j);
				degrees.set(j, afterDecrement - 1);
				numberToSubtract--;
			}
			if(numberToSubtract != 0) {
				isGraphic = false;
				break;
			}
			degrees.remove(0);
			Collections.sort(degrees);
			Collections.reverse(degrees);
		}
		//if there are any non-zero entries left, then this sequence is not graphic.
		for(Double d : degrees)
			if(d != 0)
				isGraphic = false;
		
		return isGraphic;
	}
}
